package leetcode.code1639;

public class Solution extends S1639 {

	private static int MOD = (int) 1e9 + 7;

	@Override
	public int numWays(String[] words, String target) {
		int L = words.length;
		int L1 = words[0].length();
		int L2 = target.length();
		int[][] dics = new int[L1 + 1][26];
		for (int i = 0; i < L; i++) {
			String str = words[i];
			for (int j = 1; j <= L1; j++) {
				dics[j][str.charAt(j - 1) - 'a']++;
			}
		}
		long[][] dp = new long[L2 + 1][L1 + 1];
		for (int i = 0; i <= L1; i++) {
			dp[0][i] = 1;
		}
		for (int i = 1; i <= L2; i++) {// target中第i个字符
			int to = L1 - L2 + i;
			int c = target.charAt(i - 1) - 'a';
			for (int j = i; j <= to; j++) {// 来自words中第j位置，方法数
				long cur = dics[j][c] * dp[i - 1][j - 1] + dp[i][j - 1];
				dp[i][j] = (cur + MOD) % MOD;
			}
		}
		return (int) dp[L2][L1];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug5();
		int num = 288395512 * 7 + 658683520;
		System.out.println(num);
		long numl = 288395512 * 7l + 658683520l;
		System.out.println(numl % MOD);
	}

}
